import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 强仔
 * Date: 2021-11-24
 * Time: 10:55
 */
public class TestDemo {


    /*
    * 错误
    * */
    public static boolean DFS(HashMap<Integer, Integer> map, int course, int[][] prere, boolean[] book) {
        int index = map.get(course);
        if (book[index]) {
            return false;
        }
        book[index] = true;
        int firstCourse = prere[index][1];
        if (map.get(firstCourse) == null) {
            return true;
        }
        return DFS(map, firstCourse, prere, book);
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int row = prerequisites.length;
        int col = prerequisites[0].length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < row; i++) {
            map.put(prerequisites[i][0], i);
        }
        boolean[] book = new boolean[row];
        for (int[] course : prerequisites) {
            book = new boolean[row];
            if (!DFS(map, course[0], prerequisites, book)) {
                return false;
            }
        }
        return true;
    }


    /*
     * 课程表 拓扑排序（判断是否为有向无环图）
     * DFS
     * List成链
     * visited[] 标记状态   0-未搜索 1-正在搜索 2-搜索完成
     * valid 表示有无环
     * */
    boolean valid = true;
    int[] visited;
    List<List<Integer>> lists;

    public void DFS(int u) {
        visited[u] = 1;
        for (int v : lists.get(u)) {
            int vis = visited[v];
            if (vis == 0) {
                DFS(v);
                if (!valid) {
                    return;
                }
            } else if (vis == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }

    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        lists = new ArrayList<>();
        int row = prerequisites.length;
        for (int i = 0; i < numCourses; i++) {
            lists.add(new ArrayList<>());
        }

        for (int i = 0; i < row; i++) {
            lists.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }

        visited = new int[numCourses];
        for (int i = 0; i < lists.size() && valid; i++) {
            if(visited[i] == 0) {
                DFS(i);
            }
        }
        return valid;
    }

    public static void main(String[] args) {
//        int[][] array = {{1,0},{1,2},{0,1}};
//        System.out.println(canFinish(3,array));
    }
}
